package cxydmmszl.chapter04.t075;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.HashMap;

/**
 * <li style="color: red;">Prob</li>
 * 数组中的最长连续子序列
 * <li style="color: green;">Desc</li>
 * 给定无序数组 arr，返回其中最长的连续序列的长度（要求值连续，位置可以不连续，例如 3,4,5,6 为连续的自然数）
 * <li style="color: green;">Input</li>
 * 输出两行，第一行包括一个整数 n(1≤n≤10^5)，
 * 第二行包含 n 个整数，分别代表 arr[i](1≤arr[i]≤10^8)
 * <li style="color: green;">Output</li>
 * 输出一个整数，代表最长连续子序列的长度。
 * <li style="color: blue;">Link</li> CD93
 *
 * @author habitplus
 * @since 2021-09-23 10:47
 */
public class Main {
    static StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        int len = solve2(arr);
        System.out.println(len);
    }

    private static int solve2(int[] arr) {
        if (arr == null || arr.length == 0) return 0;

        // 排序
        Arrays.sort(arr);

        int res = 1;
        int len = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] == arr[i]) continue;

            if (arr[i - 1] + 1 == arr[i]) {
                len++;
                res = Math.max(res, len);
            } else {
                // 重新计算
                len = 1;
            }
        }
        return res;
    }

    private static int solve1(int[] arr) {
        if (arr == null || arr.length == 0) return 0;

        // 哈希表
        // map，key 表示遍历过的某个数，value 代表 key 这个数所在的最长连续序列的长度。
        // 同时 map 还可以表示 arr 中的一个数之前是否出现。
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 1;
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], 1);
                // 判断前一个数是否存在
                if (map.containsKey(arr[i] - 1)) {
                    max = Math.max(max, merge(map, arr[i] - 1, arr[i]));
                }

                // 判断后一个数是否存在
                if (map.containsKey(arr[i] + 1)) {
                    max = Math.max(max, merge(map, arr[i], arr[i] + 1));
                }
            }
        }

        return max;
    }

    private static int merge(HashMap<Integer, Integer> map, int less, int more) {
        int leftNum = less - map.get(less) + 1;
        int rightNum = more + map.get(more) - 1;
        int newLen = rightNum - leftNum + 1;
        map.put(leftNum, newLen);
        map.put(rightNum, newLen);
        return newLen;
    }
}
